package com.mlh.greed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/15 11:28
 * @DESCRIPTION
 */
// 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
// 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
// 返回一个表示每个字符串片段的长度的列表。
// 输入：s = "ababcbacadefegdehijhklij"
// 输出：[9,7,8]
// 解释：
// 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
// 每个字母最多出现在一个片段中。
// 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

public class 划分字母区间 {
    //自己写出，实际上这题没什么，就是一个问题的转换
    //创建长度为26的二维数组，记录每个字符的开始和结束位置
    //剩下的就是和找重叠了，和合并区间思路一模一样
    //只是这题要处理的细节问题相对来说会多一点
    public static List<Integer> method1(String s) {
        int[][] alphabet = new int[26][2];
        List<Integer>res=new ArrayList<>();
        //将二维数组全部填充-1
        for (int i = 0; i < alphabet.length; i++) {
            Arrays.fill(alphabet[i], -1); // 填充每一行
        }
        char[] chars = s.toCharArray();
        //初始化字母表数组
        for (int i = 0; i < chars.length; i++) {
            if (alphabet[chars[i] - 'a'][0] == -1) {
                alphabet[chars[i] - 'a'][0] = i;
            }
            alphabet[chars[i] - 'a'][1] = i;
        }
        Arrays.sort(alphabet, (o1, o2) -> {
            return Integer.compare(o1[0],o2[0]);
        });
        //找到第一个有效的字母位置，-1表示这个字母没在字符串出现过
        int startIndex=-1;
        for (int i = 0; i < alphabet.length; i++) {
            if(alphabet[i][0]==-1){
                continue;
            }
            startIndex=i;
            break;
        }
        //这里开始就和合并区间一样的操作了
        int start=alphabet[startIndex][0],end=alphabet[startIndex][1];
        for (int i = startIndex+1; i < alphabet.length; i++) {
            if(end>alphabet[i][0]){
                if(end<alphabet[i][1]){
                    end=alphabet[i][1];
                }
            }else{
                res.add(end-start+1);
                start=alphabet[i][0];
                end=alphabet[i][1];
            }
        }
        res.add(end-start+1);
        return res;
    }

    //代码随想录方法
    //思路大致是一样的，但是实现的方式不一样
    //可以分为如下两步：
    // 统计每一个字符最后出现的位置（即初始化字母表）
    // 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
    public static List<Integer> method2(String s) {
        List<Integer> list = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        //他这里只记住字符的最远边界，确实，只需要记住最远边界即可
        // 因为字符的位置是固定的，不能移动，且chars数组下标就对应字符的所在位置
        for (int i = 0; i < chars.length; i++) {
            edge[chars[i] - 'a'] = i;
        }
        int idx = 0;
        int last = -1;
        for (int i = 0; i < chars.length; i++) {
            idx = Math.max(idx,edge[chars[i] - 'a']);
            if (i == idx) {
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }

    public static List<Integer> practice(String s) {
        List<Integer>res=new ArrayList<>();
        int[]cover=new int[26];
        int len =s.length();
        for (int i = 0; i < len; i++) {
            cover[s.charAt(i)-'a']=i;
        }
        int maxCover=0;
        int lastBreakPointIndex=-1;//这里设置成-1，是很聪明的，相当于在下标为-1已经分割过一次，刚好从0开始继续，这样在计算分片长度的时候很方便
        for (int i = 0; i < len; i++) {
            maxCover=Math.max(cover[s.charAt(i)-'a'],maxCover);
            if(maxCover==i){
                res.add(i-lastBreakPointIndex);
                lastBreakPointIndex=i;
            }
        }
        return res;
    }
}
